/**
 * @file     findMin.ts
 * @brief    [153. 寻找旋转排序数组中的最小值](https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/)
 * @author   Zhu
 * @date     2022-11-15 23:20
 */

/**
 * 不停地砍掉单调区间
 */
function findMin(nums: number[]): number {
    let left = 0,
        right = nums.length - 1;

    while (left < right) {
        let mid = (left + (right - left) / 2) >>> 0;
        // 因为 mid < right，又数组升序且不重复，故一定 nums[mid] < nums[right]
        if (nums[mid] < nums[right]) {
            // 因为向下取整， mid ?= left, 要保证 left < right, 故 right = mid 而非 mid - 1
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    // 此时一定是 left === right
    return nums[left];
}
